package com.mccken.practice.data_structure.data_03;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import com.mccken.practice.algorithm.common.TreeNode_Common;

/**
 * 最小公共祖先节点
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-27 23:34
 **/
public class Lca_2 {

	HashMap<TreeNode_Common, TreeNode_Common> parentNodeMap = new HashMap<>();
	Set<TreeNode_Common> visitedNodes = new HashSet<>();

	/**
	 * 1644. 二叉树的最近公共祖先 II
	 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-ii/
	 */
	public TreeNode_Common lowestCommonAncestor2(TreeNode_Common root, TreeNode_Common p, TreeNode_Common q) {
		if (p == root && q == root) {
			return root;
		}
		dfs(root);
		if (!parentNodeMap.containsKey(p) || !parentNodeMap.containsKey(q)) {
			return null;
		}

		TreeNode_Common nodeP = p;
		while (nodeP != null) {
			visitedNodes.add(nodeP);
			nodeP = parentNodeMap.get(nodeP);
		}

		TreeNode_Common nodeQ = q;
		while (!visitedNodes.contains(nodeQ)) {
			nodeQ = parentNodeMap.get(nodeQ);
		}
		return nodeQ;
	}

	private void dfs(TreeNode_Common root) {
		Queue<TreeNode_Common> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode_Common node = queue.poll();
			if (node.left != null) {
				parentNodeMap.put(node.left, node);
				queue.offer(node.left);
			}
			if (node.right != null) {
				parentNodeMap.put(node.right, node);
				queue.offer(node.right);
			}
		}
	}

}
